/* 97. 交错字符串 */
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
/* dfs */
var isInterleave = function (s1, s2, s3) {
    if (s1.length + s2.length !== s3.length) return false
    const check = (i, j, k) => { //检查i，j，k 开始的子串是否满足题目条件
        // k 越界，s3 扫描完
        if (k === s3.length) return true
        let isValid = false
        // i 没有越界，且 s1[i] 和 s3[k] 相同
        if (i < s1.length && s1[i] === s3[k]) {
            isValid = check(i + 1, j, k + 1) // i,k 右移因为一位，递归考察
        }
        //j 没有越界 且 s2[j] === s3[k] 相同
        if (j < s2.length && s2[j] === s3[k]) {
            // 有可能i,j,k 指向相同的字符 ,尝试i，k 右移
            // 如果为 true 就不执行j ,k 右移 如果是false 执行递归
            isValid = isValid || check(i, j + 1, k + 1)
        }

        return isValid
    }
    check(0, 0, 0)
};
/* 记忆化递归 */
var isInterleave = function (s1, s2, s3) {
    if (s1.length + s2.length !== s3.length) return false
    const memo = new Array(s1.length + 1).fill(0).map(() => new Array(s2.length + 1))


    const check = (i, j, k) => {
        if (memo[i][j] !== undefined) return memo[i][j]

        if (k === s3.length) return memo[i][j] = true
        let isValid = false
        if (i < s1.length && s1[i] === s3[k]) {
            isValid = check(i + 1, j, k + 1)
        }

        if (j < s2.length && s2[j] === s3[k]) {
            isValid = isValid || check(i, j + 1, k + 1)
        }

        return memo[i][j] = isValid
    }


    check(0, 0, 0)

}
// dp
var isInterleave = function (s1, s2, s3) {
    let n = s1.length, m = s2.length;
    if (m + n !== s3.length) return false;
    const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1))
    dp[0][0] = true

    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            const p = i + j - 1
            /* 
                s1的第i个元素与s3的第p个元素相等
                就取决与 s1的前 i 个元素 与 s2的前 j 个元素是否构成相等
            */
            if (i) {
                dp[i][j] = dp[i][j] || dp[i - 1][j] && s1[i - 1] == s3[p]
            }
            /* 同理 */
            if (j) {
                dp[i][j] = dp[i][j] || dp[i][j - 1] && s2[j - 1] === s3[p]
            }
        }
    }

    return dp[n][m]
}
const result = isInterleave("aabcc", "dbbca", "aadbbcbcac")
console.log("result :>>", result);